


#include <iostream>
#include <vector>
#include <stack>
using namespace std;

struct TreeNode 
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution
{
public:
    int maxProfit1(vector<int>& prices)
    {
        int res = 0;
        int n = prices.size();

        for (int i = 0; i < n; ++i)
        {
            for (int j = i + 1; j < n; ++j)
            {
                res = max(res, prices[j] - prices[i]);
            }
        }

        return res;
    }

    int maxProfit2(vector<int>& prices)
    {
        int res = 0;
        int prev_min = prices[0];

        for (int i = 0, n = prices.size(); i < n; ++i)
        {
            res = max(res, prices[i] - prev_min);
            prev_min = min(prev_min, prices[i]);
        }

        return res;
    }

    vector<int> res;
    vector<int> preorderTraversal1(TreeNode* root)
    {
        _preorderTraversal(root);

        return res;
    }

    vector<int> preorderTraversal2(TreeNode* root)
    {
        vector<int> res;
        stack<TreeNode*> st;

        for (TreeNode* cur = root; cur || st.size();)
        {
            while (cur)
            {
                res.push_back(cur->val);
                st.push(cur);
                cur = cur->left;
            }
            cur = st.top()->right;
            st.pop();
        }

        return res;
    }

private:
    void _preorderTraversal(TreeNode* root)
    {
        if (nullptr == root)
            return;

        res.push_back(root->val);
        _preorderTraversal(root->left);
        _preorderTraversal(root->right);
    }
};

int main()
{


	return 0;
}